#define _CRT_SECURE_NO_WARNINGS 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal)
    {
        if (head == nullptr)
        {
            Node* newNode = new Node(insertVal);
            newNode->next = newNode;
            return newNode;
        }

        if (head->next == head)
        {
            Node* newNode = new Node(insertVal, head);
            head->next = newNode;
            return head;
        }

        Node* cur = head->next;
        Node* prev = head;

        while (cur != head)
        {
            if ((cur->val >= insertVal && prev->val <= insertVal) ||
                (prev->val <= insertVal && cur->val < prev->val) ||
                (insertVal <= cur->val && cur->val < prev->val))
            {
                Node* newNode = new Node(insertVal, cur);
                prev->next = newNode;
                return head;
            }

            prev = prev->next;
            cur = cur->next;
        }

        Node* newNode = new Node(insertVal, cur);
        prev->next = newNode;

        return head;
    }
};